package com.jyy.prefabricated.utils;


import java.util.ArrayList;
import java.util.List;

public class TreeBuilder {

	/**
	 * 
	 * 两层循环实现建树
	 * 
	 * @param nodes 传入的树节点列表
	 * 
	 * @return
	 * 
	 */

	public static <T extends TreeNode<T>> List<T> bulid(List<T> nodes, Integer rootId) {
		List<T> trees = new ArrayList<T>();

		for (T node : nodes) {
			if (rootId == 0) {
				if(node.getPid() == 0) {
					trees.add(node);
				}
			}else {
				if(rootId.equals(node.getId())) {
					trees.add(node);
				}
			}
			
			for (T other : nodes) {
			
				if (node.getId().equals(other.getPid())) {//String慎用==判断
					
					if (node.getChildren() == null) {
						node.setChildren(new ArrayList<T>());
					}
					
					node.getChildren().add(other);
				}
			}
		}
		
		return trees;
	}

	/**
	 * 
	 * 使用递归方法建树
	 * 
	 * @param treeNodes
	 * 
	 * @return
	 * 
	 */

	public static <T extends TreeNode<T>> List<T> buildByRecursive(List<T> treeNodes, Integer rootId) {
		List<T> trees = new ArrayList<T>();

		for (T treeNode : treeNodes) {
			if(rootId == null) {
				if (treeNode.getPid() == null) {
					trees.add(findChildren(treeNode, treeNodes));
				}
			}else {
				if(rootId.equals(treeNode.getId())) {
					trees.add(findChildren(treeNode, treeNodes));
				}
			}
		}

		return trees;

	}

	/**
	 * 
	 * 递归查找子节点
	 * 
	 * @param treeNodes
	 * 
	 * @return
	 * 
	 */

	public static <T extends TreeNode<T>> T findChildren(T treeNode, List<T> treeNodes) {

		for (T it : treeNodes) {

			if (treeNode.getId().equals(it.getPid())) {

				if (treeNode.getChildren() == null) {

					treeNode.setChildren(new ArrayList<T>());

				}

				treeNode.getChildren().add(findChildren(it, treeNodes));

			}

		}

		return treeNode;

	}
	
	/**
	 * 查找id为rootId的节点的后裔节点
	 * @param <T>
	 * @param treeNodes
	 * @param rootId
	 * @return
	 */
	public static <T extends TreeNode<T>> List<T> findDescendant(List<T> treeNodes, Integer rootId){
		List<T> result = new ArrayList<T>();
		
		for(T node : treeNodes) {
			if(rootId.equals(node.getPid())){
				result.add(node);
				result.addAll(findDescendant(treeNodes, node.getId()));
			}
		}
		
		return result;
	}
	/**
	 * 查找id为rootId的节点的后裔节点
	 * @param <T>
	 * @param treeNodes
	 * @param rootId
	 * @return
	 */
	public static <T extends TreeNode<T>> List<T> findDescendants(List<T> treeNodes, Integer rootId){
		List<T> result = new ArrayList<T>();

		for(T node : treeNodes) {
			if(rootId.equals(node.getPid())){
				result.add(node);
				result.addAll(findDescendant(treeNodes, node.getId()));
			}
		}

		return result;
	}
	/**
	 * 查找节点的祖先节点
	 * @param <T>
	 * @param nodeList
	 * @param node
	 * @return
	 */
	public static <T extends TreeNode<T>> List<T> findAncestor(T node, List<T> nodeList){
		List<T> result = new ArrayList<T>();
		
		if(node == null) {
			return result;
		}
		
		T parent = findParent(node, nodeList);
		
		if(parent == null) {
			return result;
		}
		
		result.add(parent);
		result.addAll(findAncestor(parent, nodeList));
		
		return result;
	}
	
	/**
	 * 查找父亲节点
	 * @param <T>
	 * @param node
	 * @param nodeList
	 * @return
	 */
	public static <T extends TreeNode<T>> T findParent(T node, List<T> nodeList) {
		T result = null;
		
		if(node == null || node.getPid() == null) {
			return null;
		}
		
		for(T treeNode : nodeList) {
			if(node.getPid().equals(treeNode.getId())){
				result = treeNode;
				break;
			}
		}
		
		return result;
	}
}
